package Exercises.Chapter4;

import edu.princeton.cs.algs4.EdgeWeightedGraph;
import edu.princeton.cs.algs4.Edge;
import edu.princeton.cs.algs4.PrimMST;
import edu.princeton.cs.algs4.QuickUnionUF;
import java.util.ArrayList;
import java.util.Iterator;

public class e4_3_2 {
    private int count;
    
    
    public e4_3_2(){
        Edge edges[]=new Edge[10];
        edges=InitEdges(edges);
        count=0;

        for(int i=0;i<10;i++){
            for(int j=i+1;j<10;j++){
                for(int k=j+1;k<10;k++){
                    EdgeWeightedGraph graph=new EdgeWeightedGraph(8);
                    QuickUnionUF uf=new QuickUnionUF(8);

                    for(int p=0;p<10;p++){
                        if(p!=i&&p!=j&&p!=k){
                            int v=edges[p].either();
                            int w=edges[p].other(v);
                            uf.union(v,w);
                            graph.addEdge(edges[p]);
                        }
                    }

                    if(uf.count()==1){
                        count++;
                        PrintGraph(graph);
                        System.out.println();
                    }
                   
                    

                }
            }
        }

    }

    private Edge[] InitEdges(Edge edges[]){
        edges[0]=new Edge(2, 5, 1);
        edges[1]=new Edge(2, 3, 1);
        edges[2]=new Edge(5, 6, 1);
        edges[3]=new Edge(0, 3, 1);
        edges[4]=new Edge(3, 6, 1);
        edges[5]=new Edge(0, 1, 1);
        edges[6]=new Edge(3, 4, 1);
        edges[7]=new Edge(6, 7, 1);
        edges[8]=new Edge(1, 4, 1);
        edges[9]=new Edge(4, 7, 1);
        
        return edges;
    }

    public int Count(){
        return count;
    }

    private boolean HasEdge(EdgeWeightedGraph graph,int v,int w){
        Iterable<Edge> edges=graph.edges();
        Iterator<Edge> it=edges.iterator();
        
        do{
            Edge e=it.next();
            int e_v=e.either();
            int e_w=e.other(e_v);

            if(e_v==v&&e_w==w) return true;
            if(e_v==w&&e_w==v) return true;
        }while(it.hasNext());
        return false;
    }

    private void PrintGraph(EdgeWeightedGraph graph){
        System.out.print("\t\t1\t");
        if(HasEdge(graph, 0, 1)) System.out.print("---\t"); 
        else System.out.print("\t");
        System.out.print("2\n\t\t");

        if(HasEdge(graph, 0, 3)) System.out.print("|\t");
        else System.out.print("\t");
        System.out.print("\t");
        if(HasEdge(graph, 1, 4)) System.out.print("|");
        System.out.print("\t\n");
        
        System.out.print("3\t");
        if(HasEdge(graph, 2, 3)) System.out.print("---");
        System.out.print("\t4\t");
        if(HasEdge(graph, 3, 4)) System.out.print("---");
        System.out.print("\t5\n");

        if(HasEdge(graph, 2, 5)) System.out.print("|");
        System.out.print("\t\t");
        if(HasEdge(graph, 3, 6)) System.out.print("|");
        System.out.print("\t\t");
        if(HasEdge(graph, 4, 7)) System.out.print("|");
        System.out.print("\n");

        System.out.print("6\t");
        if(HasEdge(graph, 5, 6)) System.out.print("---");
        System.out.print("\t7\t");
        if(HasEdge(graph, 6, 7)) System.out.print("---");
        System.out.print("\t8\n");

    }

    public static void main(String[] args) {
        e4_3_2 e=new e4_3_2();
        System.out.println("\ntotal MSTs:"+e.Count());
    }
}
